package MyTree;

import java.util.HashMap;
import java.util.List;

/**
 * 105. 从前序与中序遍历序列构造二叉树
 *
 * 根据一棵树的前序遍历与中序遍历构造二叉树。
 *
 * 注意:
 * 你可以假设树中没有重复的元素。
 *
 * 例如，给出
 *
 * 前序遍历 preorder = [3,9,20,15,7]
 * 中序遍历 inorder = [9,3,15,20,7]
 *
 * 返回如下的二叉树：
 *
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 */
public class Leetcode0105 {
    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        // 构造哈希映射，帮助我们快速定位根节点
        HashMap<Integer, Integer> indexMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            indexMap.put(inorder[i], i);
        }
        return myBuildTree(preorder, inorder, indexMap, 0, n - 1, 0, n - 1);
    }

    public static TreeNode myBuildTree(int[] pre, int[] in, HashMap<Integer, Integer>indexMap,int pre_start, int pre_end, int in_start, int in_end){
        if (pre_start > pre_end) {
            return null;
        }

        // 前序遍历中的第一个节点就是根节点,建立根节点
        int pre_root = pre_start;
        int in_root = indexMap.get(pre[pre_root]);
        int left_len = in_root - in_start;
        TreeNode root = new TreeNode(pre[pre_root]);

        // 递归建数
        root.left = myBuildTree(pre, in, indexMap, pre_start+1, pre_start+left_len, in_start, in_root-1);
        root.right = myBuildTree(pre, in, indexMap, pre_start+left_len+1, pre_end, in_root+1, in_end);
        return root;
    }

    public static void main(String[] args) {
        int[] pre = {3,9,20,15,7};
        int[] in = {9,3,15,20,7};
        TreeNode tree = buildTree(pre, in);

        List<Integer> post = TreeUtils.postorderTraversal(tree);
        System.out.println(post.toString());
    }

}
